// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

#include <iostream>

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!
Lock::Lock(char* debugName)
{
#ifdef CHANGED
    owner = NULL;			// Lock is FREE
    name = debugName;
    queue = new List;
#endif
}

Lock::~Lock() 
{
#ifdef CHANGED
    delete queue;
#endif
}

void Lock::Acquire() 
{
#ifdef CHANGED
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    if (owner == currentThread)			// Ignore subsequent acquisition requests by the owner
    {
        (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
        return;
       
    }
    while (owner != NULL) { 			// If a non-owner thread calls acquire, it is added to
	queue->Append((void *)currentThread);	// the waiting list and is put to sleep
	currentThread->Sleep();
    } 
				
    owner = currentThread;			// This will be reached when one of the waiting threads
						// wakes up. This thread should now be the owner

    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
#endif
}

void Lock::Release() 
{
#ifdef CHANGED
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    //ASSERT (currentThread == owner);

    if (this->isHeldByCurrentThread())		// Only the owner can release a lock
    {
       thread = (Thread *)queue->Remove();	// Remove the next thread from the queue and
       if (thread != NULL)	   		// if such a thread exists
	   scheduler->ReadyToRun(thread);	// request the scheduler to put it in the ready list
       owner = NULL;				
    } 

    (void) interrupt->SetLevel(oldLevel);
#endif
}

bool Lock::isHeldByCurrentThread()
{
#ifdef CHANGED
    return (currentThread == owner);
#endif
}

Condition::Condition(char* debugName)
{ 
#ifdef CHANGED
   name = debugName;
   queue = new List;
   cvLock = NULL;
#endif
}
Condition::~Condition() 
{
#ifdef CHANGED
   delete queue;
   delete cvLock;
#endif
}
void Condition::Wait(Lock* conditionLock) 
{
#ifdef CHANGED
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    cvLock = conditionLock;		// Store the lock for comparison purposes in Signal
    conditionLock->Release();		// Release the lock in preparation for Wait, as the
					// thread will be put to sleep
    queue->Append((void *)currentThread);	// Put the current thread on the queue (Wait'ing for Signal)
    currentThread->Sleep();			// Put it to sleep
				
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts when Signal is called
    conditionLock->Acquire();			// Acquire the lock again as the thread is ready to move on
#endif

}
void Condition::Signal(Lock* conditionLock) 
{ 
#ifdef CHANGED
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    if (conditionLock != cvLock)		// Check if this is the same lock as the one used in Wait
	return;					// If not ignore the Signal, it doesn't matter how many time						// Signal is called
    Thread *thread;
    if (!conditionLock->isHeldByCurrentThread())
	return;
    thread = (Thread*)queue->Remove();		// If it is the correct lock, Remove a thread from the 
						// queue

    if (thread != NULL)				// If such a thread exists
    {
	   scheduler->ReadyToRun(thread);	// Request the scheduler to put it in the ready list
       
    }
   
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
#endif
}
void Condition::Broadcast(Lock* conditionLock) 
{
#ifdef CHANGED
	IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts

	if (conditionLock != cvLock)		// Check if this is the same lock as the one used in Wait
		return;				// If not ignore the Broadcast, it doesn't matter how many
 						// times Broadcast is called
	Thread *thread;

	thread = (Thread*)queue->Remove();

	while (thread != NULL)			// For all the threads on the queue
	{
		scheduler->ReadyToRun(thread);	// Request the scheduler to put them in the ready list
		thread = (Thread*)queue->Remove(); 

	}
	(void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
#endif
}
